All Questions
26 questions
0votes
0answers
49views
Min cost perfect matching, but with conflicting edge pairs
Consider the following variant of min-weight perfect matching. We are given a graph $G = (V,E)$ with non-negative weights on the edges. We are also given a collection of pairs of edges $P \subseteq E \...
- 649
4votes
1answer
157views
Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?
I'd like to know if the following generalization of min-cost perfect matching is NP-hard. As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
- 649
2votes
0answers
80views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined. One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 649
1vote
0answers
118views
Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?
Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
1vote
0answers
79views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
user53330
6votes
1answer
276views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard. There is also a parameterized algorithm for ...
- 9,548
3votes
1answer
63views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$. I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
- 9,548
1vote
0answers
68views
\alpha-path on Euclidean graphs
Consider the following problem: Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
6votes
0answers
184views
Statistical Algorithms vs Convex Relaxations - Planted Clique
I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
- 666
4votes
1answer
238views
Polynomial-time distinguishability threshold of planted clique
I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution $G(...
- 623
13votes
1answer
667views
Is DAG subset sum approximable?
We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$. The DAG subset sum problem (might exist under a ...
- 9,548
11votes
1answer
253views
maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph
Has this problem been studied before? Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the ...
- 769
1vote
1answer
331views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem. Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
- 233
8votes
1answer
594views
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
- 263
24votes
5answers
4kviews
Approximation algorithms for Maximum Independent Set on special classes of graphs
We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better ...
- 1,601
